A router is a networking device that forwards an incoming packet to a targeted destination. The incoming packet includes a destination IP (internet Protocol) address, which is matched against a list of entries in a table. Each entry includes an IP address prefix, a mask, and a port number. For every entry in the router table, the prefix is compared with the result of AND'ing the destination IP address with the mask. If an entry has a matching prefix, the entry supplies the port number, which indicates the next hop of the packet.
Alternatively, table entries can express the prefix and the mask in a combination called a trit representation. A trit includes an information state of “x” in addition to “1” and “0”. The state of “x” indicates a state of “don't care.” A trit representation may include several trits.
A specific example of a table follows:
PrefixMasktrit representationPort10.1.3.1255.255.255.25510.1.3.1510.1.3.0255.2055.255.010.1.3.x410.1.1.0255.255.255.0 10.12.1.x310.1.0.0255.255.0.010.1.x.x210.0.0.0255.0.0.010.x.x.x1
A destination IP address can match multiple entries of the table. For example, a destination IP address of 10.1.1.7 matches the bottom three entries in the above table. If the table returns multiple matching entries for the destination address, the correct entry is the entry including the longest matching prefix. In the previous example, the longest matching prefix is 10.1.1.0 (the trit representation 10.1.1.x).
One goal of router design is to efficiently find the entry including the longest matching prefix from multiple matching entries. The IP address has 32 bits, and the IP address prefix in CIDR (Classless InterDomain Routing) for Ipv4 (Internet Protocol Version 4) ranges in length anywhere from 1 bit to 32 bits. Thus, the destination IP address may match as many as 32 entries of the table. A router should be able to determine the entry including the longest matching prefix from as many as 32 matching entries.
One approach is to construct the table such that the table includes the entries in order, for example, starting from entries including prefixes with 32 relevant bits (i.e., a mask of 128.0.0.0). The entry including the longest matching prefix must then be the matching entry positioned earliest in the table.
One problem with this approach is that entries must be stored in predetermined positions. This leads to wasted memory space. For example, memory dedicated to entries with 32 relevant bits may be underutilized, and memory dedicated to entries with 31 relevant bits may be full; this represents a poor allocation of memory resources. Additionally, the process of updating entries may be cumbersome. For example, if memory dedicated to entries with 31 bits is full, and an additional entry of a new prefix needs to be entered into the table, then memory space must be created elsewhere, and the memory allocated to the entries with 31 bits needs to be redefined, to keep intact the scheme of ordering entries.
Therefore, what is needed is a better solution to the problem of finding an entry including the longest matching prefix from multiple matching entries.